package algorithm.array;

import util.GsonUtil;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * leetcode : https://leetcode.com/problems/pascals-triangle/description/
 * Difficulty : Easy
 *
 * 杨辉三角，也叫作帕斯卡三角
 * @Author Antony
 * @Since 2018/7/16 16:00
 */
public class PascalsTriangle {

    public static void main(String[] args) {
        List<List<Integer>> triangle = generate(5);
        System.out.println(GsonUtil.toJson(triangle));

    }

    /**
     * beats 92.9% - 1ms
     */
    public static List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<>(numRows);
        if(numRows < 1){
            return result;
        }
        int row = 0;
        result.add(Arrays.asList(1));
        while(row < numRows-1){
            row++;
            List<Integer> upList = result.get(row-1);
            List<Integer> rowList = new ArrayList<>(row);
            int currPoint = 0;
            while(currPoint <= upList.size()){
                int upLeft = currPoint-1 < 0 ? 0 : upList.get(currPoint-1);
                int upRight = currPoint==upList.size() ? 0 : upList.get(currPoint);
                rowList.add(upLeft + upRight);
                currPoint++;
            }
            // 将该列结果添加到结果集中
            result.add(rowList);
        }

        return result;
    }
}
